package com.swf.seed.algorithms.problem;

import com.swf.seed.algorithms.util.SortUtil;

/**
 * ClassName: EightQueen <br/>
 * Function: TODO ADD FUNCTION. <br/>
 * Reason: 八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。<br/>
 * 该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，<br/>
 * 即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。<br/>
 * date: 2015-1-20 下午3:09:25 <br/>
 *
 * @author shenwf10476
 * @version 
 * @since JDK 1.6
 */
public class EightQueen {
	public static int count = 0;
	/**
	 * 在第col列寻找安全的row值
	 * @param queenList
	 * @param col
	 * @return
	 */
	public void placeQueen(int[] queenList,int col){
		if (col == 8){
			System.out.println("---------"+count+++"-----------");
			SortUtil.printMap(queenList);
		}else {
			for (int i=0;i<queenList.length;i++){
				queenList[col] = i;
				if (isSafe(col, i, queenList)){
					placeQueen(queenList, col+1);
				}
			}
		}
	}
	
	/**
	 * 判断当前位置是否安全
	 * 一个皇后q(x,y)能被满足以下条件的皇后q(row,col)吃掉
	 * 1) x=row(在纵向不能有两个皇后)
	 * 2) y=col（横向）
 	 * 3) col + row = y+x;（斜向正方向）
	 * 4) col - row = y-x;（斜向反方向）

	 * @param col
	 * @param row
	 * @param queenList
	 * @return
	 */
	boolean isSafe(int col,int row,int[] queenList){
		for (int tempCol = 0;tempCol<col;tempCol++){
			int tempRow = queenList[tempCol];
			if (tempRow == row){
				return false;
			}
			if (tempCol == col){
				return false;
			}
			if (tempRow - tempCol == row - col || tempRow + tempCol == row + col){
				return false;
			}
		}
		return true;
	}
	
	public static void main(String[] args) {
		EightQueen queen = new EightQueen();
		int[] queenList = new int[8];
		queen.placeQueen(queenList, 0);
	}
}
